The minimum graph bisection problem is a well known problem that seeks to partition a graph into two equally-sized cells while minimizing the number of edges between them. More particularly, the input to the minimum graph bisection problem is an undirected, unweighted graph G=(V, E), and its goal is to partition V into two sets A and B such that |A|, |B|≦┌|V|/2┐, and the number of edges between A and B (the cut size) is minimized. This combinatorial optimization problem is a case of graph partitioning which asks for arbitrarily many cells. It has many applications, including image processing, computer vision, divide-and-conquer algorithms, VLSI circuit layout, distributed computing, and route planning.
Known software libraries (e.g., METIS, SCOTCH, JOSTLE, etc.) solve the graph partitioning problem but the quality of the obtained solutions is often unacceptable. Heuristics directed to particular graph classes, such as DibaP (for meshes) and PUNCH (for road networks), are also known. These techniques cannot prove optimality or provide approximation guarantees, and do not perform well unless imbalance is allowed.
There is much literature on computing exact solutions to the graph bisection and partitioning problems, mostly using the branch-and-bound framework. These techniques can only solve instances of moderate size (with hundreds or a few thousand vertices) to optimality, even after a few hours of processing.